#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct tnode {
    char *word;
    int count;
    struct tnode *left;
    struct tnode *right;
} Tree;
    
Tree *talloc(void)
{
    return (Tree *)malloc(sizeof(Tree));
}

Tree *addtree(Tree *pTree, char *wd)
{
    int comp = 0;
    if(pTree == NULL){ //tree is not exit and create a tree root
        pTree = talloc();
        pTree->word = strdup(wd);
        pTree->count = 1;
        pTree->left = NULL;
        pTree->right = NULL;
    }else if((comp = strcmp(wd, pTree->word)) == 0){
        pTree->count++;
    }else if(comp < 0){
        pTree->left = addtree(pTree->left, wd);
    }else{
        pTree->right = addtree(pTree->right, wd);
    }   

    return pTree;
}

void treeprint(Tree *pTree)
{
    if(pTree == NULL){
        return;
    }else{
        treeprint(pTree->left);
        printf("%4d %s\n", pTree->count, pTree->word);       
        treeprint(pTree->right);
    }
}

#define MAXWORD 100

#define BUFSIZE 100
char buf[BUFSIZE];
int bufp = 0;
int getch(void)
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(int c)
{
    if(bufp >= BUFSIZE)
        printf("ungetch: too many characters\n");
    else
    {
        buf[bufp++] = c;
    }    
}

int getword(char *word, int lim)
{
    char *w = word;
    char c;

    do{
        c = getch();
    }
    while (isspace(c));

    if(c != EOF){
        *w++ = c;
    }
    if(!isalpha(c) && c != '_' && c != '#' && c != '"'){
        *w = '\0';
        return c;               
    }

    for(; --lim > 0; w++){
        *w = getch();
  
        if(!isalnum(*w) && *w != '_' && *w != '"'){
            ungetch(*w);
            break;
        }        
    }
    *w = '\0';
    return word[0];
}

int main()
{
    Tree *root = NULL;
    char word[MAXWORD];

    while (getword(word, MAXWORD) != EOF){
        if(isalpha(word[0])){
            root = addtree(root, word);
        }
    }

    treeprint(root);
    
    return 0;
}